package com.fanco.learn_datastruct_leetcode.leetcode;
import java.util.Arrays;
/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 * eg1: nums=[1,2,3] output: [1,3,2]
 * eg2: nums=[3,2,1] output: [1,2,3]
 * eg3: nums=[1,1,5] output: [1,5,1]
 *
 */
public class Day16 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int []nums = {1,2,3,4,5,6};
        for (int i = 0 ; i <10 ;i ++) {
            solution.nextPermutation(nums);
            System.out.println(Arrays.toString(nums));
        }
    }
    private static class Solution {
        public void nextPermutation(int[] nums) {
            /**
             * 如果当前nums的数据时按照升序排列的，[1,2,3,4,5,6]
             * 那它的下一个排列就是从数组后面最后一位开始  较大的数 与  相邻的数相互交换位置 [1,2,3,4,6,5]
             * 可以看出都是 从后往前，找前一个数比后一个数小 以这个前一个数的位置作为标记分割[1,2,3,4] [6,5]
             * 找到 4(当前位置) 与后面的数组从后往前依次比较，找到比他大的数据。 这里 为 5 交换他们两的位置  1,2,3,5,6,4
             * 再讲数组的[6,4] 按照倒序翻转. 1,2,3,5,4,6  这个就是下一个更大的排列
             * 1,2,3,5,6,4
             * 1,2,3,6,4,5
             */
            if (nums.length < 2) {
                return;
            }
            // 找到符合的指标位置
            int i = nums.length - 2;  // 取倒数第二位开始
            // 找到某个数比他的后一位小
            while (i >= 0 && nums[i] >= nums[i+1]) {
                i--;
            }
            // 如果找到,
            if (i >= 0) {
                int j = nums.length -1; // 倒数第一位
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }
        public void swap(int [] nums, int i, int j ) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        /**
         * 翻转就是将左右的数据两两交换
         * @param nums
         * @param start
         */
        public void reverse(int[] nums, int start) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }
}
